package com.ztom.top100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 二叉树的序列化与反序列化
 * <p>
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 *
 * @author ZhangTao
 */
public class Code75Codec {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return null;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            TreeNode node = null;
            StringBuilder builder = new StringBuilder();
            while (!queue.isEmpty()) {
                node = queue.poll();
                if (node == null) {
                    builder.append("#,");
                } else {
                    builder.append(node.val).append(",");
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            return builder.deleteCharAt(builder.length() - 1).toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode head = generateNode(nodes.poll());
            queue.add(head);
            TreeNode node = null;
            while (!queue.isEmpty()) {
                node = queue.poll();
                if (node == null) {
                    continue;
                }
                node.left = generateNode(nodes.poll());
                queue.add(node.left);
                node.right = generateNode(nodes.poll());
                queue.add(node.right);
            }
            return head;
        }

        private TreeNode generateNode(String str) {
            if (str == null || "#".equals(str)) {
                return null;
            }
            return new TreeNode(Integer.parseInt(str));
        }
    }
}
